/*
 * @lc app=leetcode.cn id=1001 lang=cpp
 *
 * [1001] 网格照明
 */

// @lc code=start
class Solution
{
public:
    vector<int> gridIllumination(int n, vector<vector<int>> &lamps, vector<vector<int>> &queries)
    {
        unordered_map<int, int> row, col, diagnoal, anti_diagnoal;
        auto hash_p = [](const pair<int, int> &p) -> size_t
        {
            static hash<long long> h;
            return h(p.first + (static_cast<long long>(p.second) << 32));
        };
        unordered_set<pair<int, int>, decltype(hash_p)> lampsPointer(0, hash_p);

        for (auto &lamp : lamps)
        {
            if (lampsPointer.count({lamp[0], lamp[1]}) > 0)
            {
                continue;
            }
            lampsPointer.insert({lamp[0], lamp[1]});
            row[lamp[0]]++;
            col[lamp[1]]++;
            diagnoal[lamp[0] - lamp[1]]++;
            anti_diagnoal[lamp[0] + lamp[1]]++;
        }

        int m = queries.size();
        vector<int> ans(m, 0);
        for (int i = 0; i < m; i++)
        {
            int r = queries[i][0], c = queries[i][1];
            if (row.count(r) > 0 && row[r] > 0)
            {
                ans[i] = 1;
            }
            else if (col.count(c) > 0 && col[c] > 0)
            {
                ans[i] = 1;
            }
            else if (diagnoal.count(r - c) > 0 && diagnoal[r - c] > 0)
            {
                ans[i] = 1;
            }
            else if (anti_diagnoal.count(r + c) > 0 && anti_diagnoal[r + c] > 0)
            {
                ans[i] = 1;
            }
            for (int x = r - 1; x <= r + 1; x++)
            {
                for (int y = c - 1; y <= c + 1; y++)
                {
                    if (x < 0 || y < 0 || x >= n || y >= n)
                    {
                        continue;
                    }

                    auto p = lampsPointer.find({x, y});
                    if (p != lampsPointer.end())
                    {
                        lampsPointer.erase(p);
                        row[x]--;
                        col[y]--;
                        diagnoal[x - y]--;
                        anti_diagnoal[x + y]--;
                    }
                }
            }
        }
        return ans;
    }
};
// @lc code=end
